#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>


////给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//struct ListNode* reverseList(struct ListNode* head) {
//    if (head == NULL)
//    {
//        return NULL;
//    }
//    struct ListNode* n1, * n2, * n3;
//    n1 = NULL;
//    n2 = head;
//    n3 = head->next;
//
//    while (n2)
//    {
//        n2->next = n1;
//
//        n1 = n2;
//        n2 = n3;
//
//        if (n3)
//        {
//            n3 = n3->next;
//        }
//    }
//    return n1;
//}


////将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    if (list1 == NULL)
//    {
//        return list2;
//    }
//    if (list2 == NULL)
//    {
//        return list1;
//    }
//
//    struct ListNode* newhead = NULL, * tail = NULL;
//    while (list1 && list2)
//    {
//        if (list1->val < list2->val)
//        {
//            if (tail == NULL)
//            {
//                tail = newhead = list1;
//            }
//            else
//            {
//                tail->next = list1;
//                tail = tail->next;
//            }
//            list1 = list1->next;
//        }
//        else
//        {
//            if (tail == NULL)
//            {
//                tail = newhead = list2;
//            }
//            else
//            {
//                tail->next = list2;
//                tail = tail->next;
//            }
//            list2 = list2->next;
//        }
//    }
//    if (list1)
//    {
//        tail->next = list1;
//    }
//    if (list2)
//    {
//        tail->next = list2;
//    }
//    return newhead;
//}

//现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//#include <cstddef>
//#include <cstdlib>
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        struct ListNode* head1, * tail1, * head2, * tail2;
//        head1 = tail1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//        head2 = tail2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//        struct ListNode* cur = pHead;
//
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                tail1->next = cur;
//                tail1 = tail1->next;
//            }
//            else
//            {
//                tail2->next = cur;
//                tail2 = tail2->next;
//            }
//            cur = cur->next;
//        }
//        tail1->next = head2->next;
//
//        tail2->next = NULL;
//
//        pHead = head1->next;
//        free(head1);
//        free(head2);
//
//        return pHead;
//    }
//};



//对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//class PalindromeList {
//public:
//    struct ListNode* reverseList(struct ListNode* head)
//    {
//        struct ListNode* cur = head;
//        struct ListNode* newhead = NULL;
//
//        while (cur)
//        {
//            struct ListNode* next = cur->next;
//
//            cur->next = newhead;
//            newhead = cur;
//            cur = next;
//        }
//        return newhead;
//    }
//
//    struct ListNode* middleNode(struct ListNode* head)
//    {
//        struct ListNode* slow = head, * fast = head;
//        while (fast && fast->next) {
//            slow = slow->next;
//            fast = fast->next->next;
//        }
//        return slow;
//    }
//
//    bool chkPalindrome(ListNode* head)
//    {
//        struct ListNode* mid = middleNode(head);
//        struct ListNode* rhead = reverseList(mid);
//
//        while (head && rhead) {
//            if (head->val != rhead->val)
//                return false;
//            head = head->next;
//            rhead = rhead->next;
//        }
//        return true;
//    }
//};



//给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，
//评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 - 1，
//则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//struct ListNode* detectCycle(struct ListNode* head)
//{
//    struct ListNode* slow, * fast;
//    slow = fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//
//        if (slow == fast)
//        {
//            struct ListNode* meet = slow;
//            while (head != meet)
//            {
//                head = head->next;
//                meet = meet->next;
//            }
//            return meet;
//        }
//    }
//    return NULL;
//}


//给你一个链表的头节点 head ，判断链表中是否有环。
//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 
// 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
// 注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
//如果链表中存在环 ，则返回 true 。 否则，返回 false 。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//bool hasCycle(struct ListNode* head) {
//    struct ListNode* slow = head, * fast = head;
//
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//
//        if (slow == fast)
//        {
//            return true;
//        }
//    }
//
//    return false;
//}

//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//    struct ListNode* curA = headA, * curB = headB;
//    int lenA = 1;
//    int lenB = 1;
//
//    while (curA->next)
//    {
//        curA = curA->next;
//        lenA++;
//    }
//    while (curB->next)
//    {
//        curB = curB->next;
//        lenB++;
//    }
//
//    if (curA != curB)
//    {
//        return NULL;
//    }
//
//    int n = abs(lenA - lenB);
//    struct ListNode* Longlist = headA, * Shortlist = headB;
//
//    if (lenB > lenA)
//    {
//        Longlist = headB;
//        Shortlist = headA;
//    }
//
//    while (n--)
//    {
//        Longlist = Longlist->next;
//    }
//
//    while (Longlist != Shortlist)
//    {
//        Longlist = Longlist->next;
//        Shortlist = Shortlist->next;
//    }
//
//    return Longlist;
//}


//.给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur = head;
    while (cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));

        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;

        cur = cur->next->next;
    }

    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        if (cur->random != NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }

        cur = cur->next->next;
    }

    struct Node* newhead = NULL, * tail = NULL;

    cur = head;

    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

        if (tail == NULL)
        {
            newhead = tail = copy;
        }
        else
        {
            tail->next = copy;
            tail = tail->next;
        }

        cur->next = next;
        cur = next;
    }
    return newhead;
}